import collections
class Solution(object):
    def possibleBipartition(self, n, dislikes):
        d = collections.defaultdict(set)
        p = [0] * (n + 1)
        for pair in dislikes:
            d[pair[0]].add(pair[1])
            d[pair[1]].add(pair[0])
        def search(u, state):
            p[u] = state
            for v in d[u]:
                if not p[v]:
                    flag = search(v, 3 - state)
                    if not flag:
                        return False
                else:
                    if p[v] == state:
                        return False
            return True
        for i in range(n):
            if not p[i]:
                flag = search(i, 1)
                if not flag:
                    return False
        return True


data = Solution()
n = 4
dislikes = [[1, 2], [1, 3], [2, 4]]
print(data.possibleBipartition(n, dislikes))
